#pragma once

class PathFinder
{
public:
	PathFinder();

	bool Find (const StageMap& map, int beginIdx, int endIdx, MapPath& path);
	void Explore(const StageMap& map, int start, int block, dynamic_bitset& brickBits) const;

private:
	//===============================
	struct Node
	{
		int Cost;
		int Total;
		int Parent;
	};

	//===============================
	class OpenList 
	{
	public:
		OpenList (std::vector<Node>& mapNodes):_mapNodes(mapNodes),_usedBrick(mapNodes.size()) {}
		bool IsEmpty() const { return _queue.empty(); }
		bool Contain(int idx) const { return _usedBrick[idx]; }

		void Push (int idx)
		{
			_usedBrick[idx] = true;
			_queue.push(OpenListNode(idx, _mapNodes[idx].Total));
		}

		int Pop()
		{
			assert (!IsEmpty());

			int idx =_queue.top().Idx;
			_queue.pop();
			_usedBrick[idx] = false;

			return idx;
		}

	private:
		//===============================
		struct OpenListNode
		{
			OpenListNode(int idx, int cost)
				:Idx((short)idx),Cost((short)cost)
			{}

			short Idx;
			short Cost;
		};

		//===============================
		struct OpenListNodeComp
		{
			bool operator()(const OpenListNode& a, const OpenListNode& b) const
			{
				return a.Cost > b.Cost;
			}
		};

		//===============================
		std::vector<Node>&			_mapNodes;
		dynamic_bitset				_usedBrick;
		std::priority_queue<OpenListNode, std::vector<OpenListNode>, OpenListNodeComp>	_queue;
	};

	//===============================
	void FillPath (const StageMap& map, int beginIdx, int endIdx, MapPath& path);

	std::vector<Node>	_mapNodes;
};
